package highfreq;

import java.util.Arrays;

public class item215 {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        int index = nums.length-k;
        int res = nums[index];
        return res;
    }
    public static int findKthLargest1(int[] nums, int k) {
        int left = 0;
        int right = nums.length-1;
        int target = nums.length-k;
        while (left<right)
        {
           int index= quick(nums,left,right);
           if(index==target)
           {
               return nums[index];
           }
           if(index<target)
           {
               left = index+1;
           }
           if(index>target)
           {
               right = index-1;
           }
        }
       return -1;
    }

    private static int quick(int[] nums, int left, int right) {
        int temp = nums[left];
        int i = left;
        int j = right;
        while (i<j)
        {
            while (i<j&&temp<=nums[j])j--;
            while (i<j&&temp>nums[i]) i++;
            if(i<j)
            {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] =tmp;
            }
        }

        nums[left] =nums[i];
        nums[i] = temp;
        return i;
    }

    public static void main(String[] args) {
      int [] nums = {3,2,3,1,2,4,5,5,6};
      findKthLargest1(nums,4);
    }

}
